#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
const int MAXN=1e6+10;
LL n,a[MAXN],f[MAXN],q[MAXN];
db slope(LL j,LL k)
{
	return (f[j]-f[k]+(j*j+j-k*k-k)/2.0)*1.0/(j-k);
}
int main()
{
	scanf("%lld",&n);
	for(LL i=1;i<=n;++i)scanf("%lld",&a[i]);
	LL l=0,r=0;
	for(LL i=1;i<=n;++i)
	{
		while(l<r&&slope(q[l],q[l+1])<i)++l;
		LL t=q[l];
		f[i]=f[t]+(i-t)*(i-t-1)/2+a[i];
		while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i))--r;
		q[++r]=i;
	}
	printf("%lld\n",f[n]);
	return 0;
}
